#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class WordDictionary{
    private:
    struct TreeNode{
        vector<TreeNode*> children;
        bool isEnd;
        TreeNode(): children(26, nullptr), isEnd(false){}
    };
    TreeNode* trie;

    bool dfs(string word, int index, TreeNode* node){
        if(index == word.size()){
            return node->isEnd;
        }
        char ch = word[index];
        if(ch >= 'a' && ch <= 'z'){
            TreeNode* child = node->children[ch-'a'];
            if(child != nullptr && dfs(word, index+1, child)){
                return true;
            }
        }else if(ch == '.'){
            for(int i = 0; i != 26; i++){
                TreeNode* child = node->children[i];
                if(child != nullptr && dfs(word, index+1, child)){
                    return true;
                }
            }
        }
        return false;
    }
    
    public:
    WordDictionary(){
        trie = new TreeNode();
    }

    void addWord(string word){
        TreeNode* node = trie;
        for(char ch: word){
            ch = ch - 'a';
            if(node->children[ch] == nullptr){
                node->children[ch] = new TreeNode();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word){
        TreeNode* node = trie;
        return dfs(word, 0, node);
    }

};

void test(){
    WordDictionary* s = new WordDictionary();
    s->addWord("bad");
    s->addWord("dad");
    s->addWord("mad");
    cout << s->search("pad") << endl;
    cout << s->search("bad") << endl;
    cout << s->search(".ad") << endl;
    cout << s->search("b..") << endl;
}

int main(void){
    test();

    return 0;
}